package william.hash;

import java.util.HashSet;
import java.util.Set;

/**
 * @author ZhangShenao
 * @date 2024/3/5
 * @description
 */
public class Leetcode202_快乐数 {
    /**
     * 借助Set实现
     * 每次数字n各位的平方和,并保存在Set中
     * 如果计算结果==1,说明为快乐数
     * 如果计算结果出现在了Set中,则说明出现了循环,则为非快乐数
     * <p>
     * 时间复杂度O(logN)
     * 空间复杂度O(logN)
     */
    public boolean isHappy(int n) {
        //边界条件校验
        if (n <= 0) {
            return false;
        }
        if (n == 1) {
            return true;
        }

        //使用一个Set保存中间计算结果
        Set<Integer> history = new HashSet<>();
        history.add(n);

        //计算平方和,判断是否出现了1
        while (n != 1) {
            n = calcSqrtSum(n);
            if (history.contains(n)) {
                return false;
            }
            history.add(n);
        }

        //出现1退出循环,找到快乐数
        return true;
    }

    /**
     * 计算数字n的平方和
     */
    private int calcSqrtSum(int n) {
        int sum = 0;
        while (n != 0) {
            int v = n % 10;
            sum += v * v;
            n = n / 10;
        }
        return sum;
    }

    public static void main(String[] args) {
        Leetcode202_快乐数 s = new Leetcode202_快乐数();
        System.out.println(s.isHappy(19));
    }
}
